home *** CD-ROM | disk | FTP | other *** search
/ PC World Interactive 7 / PC World Interactive 7.iso / program / cprog.EXE / COMPRESS.TXT < prev    next >
Text File  |  1995-12-05  |  13KB  |  280 lines

  1.  
  2.          Data Compression Algorithms of LARC and LHarc
  3.                       Haruhiko Okumura*
  4. *The author is the sysop of the Science SIG of PV-VAN.  His
  5.  address is: 12-2-404 Green Heights, 580 Nagasawa, Yokosuka 239
  6.  Japan
  7. ---------------------------------------------------------------
  8.  
  9. 1. Introduction
  10.  
  11. In the spring of 1988, I wrote a very simple data compression program
  12. named LZSS in C language, and uploaded it to the Science SIG (forum) of
  13. PC-VAN, Japan's biggest personal computer network. 
  14.  
  15. That program was based on Storer and Szymanski's slightly modified
  16. version of one of Lempel and Ziv's algorithms.  Despite its simplicity,
  17. for most files its compression outperformed the archivers then widely
  18. used. 
  19.  
  20. Kazuhiko Miki rewrote my LZSS in Turbo Pascal and assembly language, and
  21. soon made it evolve into a complete archiver, which he named LARC. 
  22.  
  23. The first versions of LZSS and LARC were rather slow.  So I rewrote my
  24. LZSS using a binary tree, and so did Miki.  Although LARC's encoding was
  25. slower than the fastest archiver available, its decoding was quite fast,
  26. and its algorithm was so simple that even self-extracting files
  27. (compressed files plus decoder) it created were usually smaller than
  28. non-self-extracting files from other archivers. 
  29.  
  30. Soon many hobby programmers joined the archiver project at the forum. 
  31. Very many suggestions were made, and LARC was revised again and again. 
  32. By the summer of 1988, LARC's speed and compression have improved so
  33. much that LARC-compressed programs were beginning to be uploaded in many
  34. forums of PC-VAN and other networks. 
  35.  
  36. In that summer I wrote another program, LZARI, which combined the LZSS
  37. algorithm with adaptive arithmetic compression.  Although it was slower
  38. than LZSS, its compression performance was amazing. 
  39.  
  40. Miki, the author of LARC, uploaded LZARI to NIFTY-Serve, another big
  41. information network in Japan.  In NIFTY-Serve, Haruyasu Yoshizaki
  42. replaced LZARI's adaptive arithmetic coding with a version of adaptive
  43. Huffman coding to increase speed.  Based on this algorithm, which he
  44. called LZHUF, he developed yet another archiver, LHarc. 
  45.  
  46. In what follows, I will review several of these algorithms and supply
  47. simplified codes in C language. 
  48.  
  49. 2. Simple coding methods
  50.  
  51. Replacing several (usually 8 or 4) "space" characters by one "tab"
  52. character is a very primitive method for data compression.  Another
  53. simple method is run-length coding, which encodes the message
  54. "AAABBBBAACCCC" into "3A4B2A4C", for example. 
  55.  
  56. 3. LZSS coding
  57.  
  58. This scheme is initiated by Ziv and Lempel [1].  A slightly modified
  59. version is described by Storer and Szymanski [2].  An implementation
  60. using a binary tree is proposed by Bell [3].  The algorithm is quite
  61. simple: Keep a ring buffer, which initially contains "space" characters
  62. only.  Read several letters from the file to the buffer.  Then search
  63. the buffer for the longest string that matches the letters just read,
  64. and send its length and position in the buffer. 
  65.  
  66. If the buffer size is 4096 bytes, the position can be encoded in 12
  67. bits.  If we represent the match length in four bits, the <position,
  68. length> pair is two bytes long.  If the longest match is no more than
  69. two characters, then we send just one character without encoding, and
  70. restart the process with the next letter.  We must send one extra bit
  71. each time to tell the decoder whether we are sending a <position,
  72. length> pair or an unencoded character. 
  73.  
  74. The accompanying file LZSS.C is a version of this algorithm.  This
  75. implementation uses multiple binary trees to speed up the search for the
  76. longest match.  All the programs in this article are written in
  77. draft-proposed ANSI C.  I tested them with Turbo C 2.0. 
  78.  
  79. 4. LZW coding
  80.  
  81. This scheme was devised by Ziv and Lempel [4], and modified by Welch
  82. [5]. 
  83.  
  84. The LZW coding has been adopted by most of the existing archivers, such
  85. as ARC and PKZIP.  The algorithm can be made relatively fast, and is
  86. suitable for hardware implementation as well. 
  87.  
  88. The algorithm can be outlined as follows: Prepare a table that can
  89. contain several thousand items.  Initially register in its 0th through
  90. 255th positions the usual 256 characters.  Read several letters from the
  91. file to be encoded, and search the table for the longest match.  Suppose
  92. the longest match is given by the string "ABC".  Send the position of
  93. "ABC" in the table.  Read the next character from the file.  If it is
  94. "D", then register a new string "ABCD" in the table, and restart the
  95. process with the letter "D".  If the table becomes full, discard the
  96. oldest item or, preferably, the least used. 
  97.  
  98. A Pascal program for this algorithm is given in Storer's book [6]. 
  99.  
  100. 5. Huffman coding
  101.  
  102. Classical Huffman coding is invented by Huffman [7].  A fairly readable
  103. accound is given in Sedgewick [8]. 
  104.  
  105. Suppose the text to be encoded is "ABABACA", with four A's, two B's, and
  106. a C.  We represent this situation as follows:
  107.  
  108.         4    2    1
  109.         |    |    |
  110.         A    B    C
  111.  
  112. Combine the least frequent two characters into one, resulting in the new
  113. frequency 2 + 1 = 3:
  114.  
  115.         4      3
  116.         |     /  \
  117.         A    B    C
  118.  
  119. Repeat the above step until the whole characters combine into a tree:
  120.  
  121.             7
  122.           /  \
  123.          /     3
  124.         /    /  \
  125.        A    B    C
  126.  
  127. Start at the top ("root") of this encoding tree, and travel to the
  128. character you want to encode.  If you go left, send a "0"; otherwise
  129. send a "1".  Thus, "A" is encoded by "0", "B" by "10", "C" by "11". 
  130. Algotether, "ABABACA" will be encoded into ten bits, "0100100110". 
  131.  
  132. To decode this code, the decoder must know the encoding tree, which must
  133. be sent separately. 
  134.  
  135. A modification to this classical Huffman coding is the adaptive, or
  136. dynamic, Huffman coding.  See, e.g., Gallager [9].  In this method, the
  137. encoder and the decoder processes the first letter of the text as if the
  138. frequency of each character in the file were one, say.  After the first
  139. letter has been processed, both parties increment the frequency of that
  140. character by one.  For example, if the first letter is 'C', then
  141. freq['C'] becomes two, whereas every other frequencies are still one. 
  142. Then the both parties modify the encoding tree accordingly.  Then the
  143. second letter will be encoded and decoded, and so on. 
  144.  
  145. 6. Arithmetic coding
  146.  
  147. The original concept of arithmetic coding is proposed by P.  Elias.  An
  148. implementation in C language is described by Witten and others [10]. 
  149.  
  150. Although the Huffman coding is optimal if each character must be encoded
  151. into a fixed (integer) number of bits, arithmetic coding wins if no such
  152. restriction is made. 
  153.  
  154. As an example we shall encode "AABA" using arithmetic coding.  For
  155. simplicity suppose we know beforehand that the probabilities for "A" and
  156. "B" to appear in the text are 3/4 and 1/4, respectively. 
  157.  
  158. Initially, consider an interval:
  159.  
  160.               0 <= x < 1.
  161.  
  162. Since the first character is "A" whose probability is 3/4, we shrink the
  163. interval to the lower 3/4:
  164.  
  165.               0 <= x < 3/4.
  166.  
  167. The next character is "A" again, so we take the lower 3/4:
  168.  
  169.               0 <= x < 9/16.
  170.  
  171. Next comes "B" whose probability is 1/4, so we take the upper 1/4:
  172.  
  173.               27/64 <= x < 9/16,
  174.  
  175. because "B" is the second element in our alphabet, {A, B}.  The last
  176. character is "A" and the interval is
  177.  
  178.               27/64 <= x < 135/256,
  179.  
  180. which can be written in binary notation
  181.  
  182.               0.011011 <= x < 0.10000111.
  183.  
  184. Choose from this interval any number that can be represented in fewest
  185. bits, say 0.1, and send the bits to the right of "0."; in this case we
  186. send only one bit, "1".  Thus we have encoded four letters into one bit!
  187. With the Huffman coding, four letters could not be encoded into less
  188. than four bits. 
  189.  
  190. To decode the code "1", we just reverse the process: First, we supply
  191. the "0." to the right of the received code "1", resulting in "0.1" in
  192. binary notation, or 1/2.  Since this number is in the first 3/4 of the
  193. initial interval 0 <= x < 1, the first character must be "A".  Shrink
  194. the interval into the lower 3/4.  In this new interval, the number 1/2
  195. lies in the lower 3/4 part, so the second character is again "A", and so
  196. on.  The number of letters in the original file must be sent separately
  197. (or a special 'EOF' character must be appended at the end of the file). 
  198.  
  199. The algorithm described above requires that both the sender and receiver
  200. know the probability distribution for the characters.  The adaptive
  201. version of the algorithm removes this restriction by first supposing
  202. uniform or any agreed-upon distribution of characters that approximates
  203. the true distribution, and then updating the distribution after each
  204. character is sent and received. 
  205.  
  206. 7. LZARI
  207.  
  208. In each step the LZSS algorithm sends either a character or a <position,
  209. length> pair.  Among these, perhaps character "e" appears more
  210. frequently than "x", and a <position, length> pair of length 3 might be
  211. commoner than one of length 18, say.  Thus, if we encode the more
  212. frequent in fewer bits and the less frequent in more bits, the total
  213. length of the encoded text will be diminished.  This consideration
  214. suggests that we use Huffman or arithmetic coding, preferably of
  215. adaptive kind, along with LZSS. 
  216.  
  217. This is easier said than done, because there are many possible
  218. <position, length> combinations.  Adaptive compression must keep running
  219. statistics of frequency distribution.  Too many items make statistics
  220. unreliable. 
  221.  
  222. What follows is not even an approximate solution to the problem posed
  223. above, but anyway this was what I did in the summer of 1988. 
  224.  
  225. I extended the character set from 256 to three-hundred or so in size,
  226. and let characters 0 through 255 be the usual 8-bit characters, whereas
  227. characters 253 + n represent that what follows is a position of string
  228. of length n, where n = 3, 4 , ....  These extended set of characters
  229. will be encoded with adaptive arithmetic compression. 
  230.  
  231. I also observed that longest-match strings tend to be the ones that were
  232. read relatively recently.  Therefore, recent positions should be encoded
  233. into fewer bits.  Since 4096 positions are too many to encode
  234. adaptively, I fixed the probability distribution of the positions "by
  235. hand." The distribution function given in the accompanying LZARI.C is
  236. rather tentative; it is not based on thorough experimentation.  In
  237. retrospect, I could encode adaptively the most significant 6 bits, say,
  238. or perhaps by some more ingenious method adapt the parameters of the
  239. distribution function to the running statistics. 
  240.  
  241. At any rate, the present version of LZARI treats the positions rather
  242. separately, so that the overall compression is by no means optimal. 
  243. Furthermore, the string length threshold above which strings are coded
  244. into <position, length> pairs is fixed, but logically its value must
  245. change according to the length of the <position, length> pair we would
  246. get. 
  247.  
  248. 8. LZHUF
  249.  
  250. LZHUF, the algorithm of Haruyasu Yoshizaki's archiver LHarc, replaces
  251. LZARI's adaptive arithmetic coding with adaptive Huffman.  LZHUF encodes
  252. the most significant 6 bits of the position in its 4096-byte buffer by
  253. table lookup.  More recent, and hence more probable, positions are coded
  254. in less bits.  On the other hand, the remaining 6 bits are sent
  255. verbatim.  Because Huffman coding encodes each letter into a fixed
  256. number of bits, table lookup can be easily implemented. 
  257.  
  258. Though theoretically Huffman cannot exceed arithmetic compression, the
  259. difference is very slight, and LZHUF is fairly fast. 
  260.  
  261. The accompanying file LZHUF.C was written by Yoshizaki.  I translated
  262. the comments into English and made a few trivial changes to make it
  263. conform to the ANSI C standard. 
  264.  
  265. References
  266.   [1] J. Ziv and A. Lempel, IEEE Trans. IT-23, 337-343 (1977).
  267.   [2] J. A. Storer and T. G. Szymanski, J. ACM, 29, 928-951
  268.       (1982).
  269.   [3] T. C. Bell, IEEE Trans. COM-34, 1176-1182 (1986).
  270.   [4] J. Ziv and A. Lempel, IEEE Trans. IT-24, 530-536 (1978).
  271.   [5] T. A. Welch, Computer, 17, No.6, 8-19 (1984).
  272.   [6] J. A. Storer, Data Compression: Methods and Theory
  273.       (Computer Science Press, 1988).
  274.   [7] D. A. Huffman, Proc IRE 40, 1098-1101 (1952).
  275.   [8] R. Sedgewick, Algorithms, 2nd ed. (Addison-Wesley, 1988).
  276.   [9] R. G. Gallager, IEEE Trans. IT-24, 668-674 (1978).
  277.  [10] I. E. Witten, R. M. Neal, and J. G. Cleary, Commun. ACM
  278.       30, 520-540 (1987).
  279.  
  280.